{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Combination Sum II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #backtracking"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #回溯"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: combinationSum2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #组合总和 II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个候选人编号的集合&nbsp;<code>candidates</code>&nbsp;和一个目标数&nbsp;<code>target</code>&nbsp;，找出&nbsp;<code>candidates</code>&nbsp;中所有可以使数字和为&nbsp;<code>target</code>&nbsp;的组合。</p>\n",
    "\n",
    "<p><code>candidates</code>&nbsp;中的每个数字在每个组合中只能使用&nbsp;<strong>一次</strong>&nbsp;。</p>\n",
    "\n",
    "<p><strong>注意：</strong>解集不能包含重复的组合。&nbsp;</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例&nbsp;1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> candidates =&nbsp;<code>[10,1,2,7,6,1,5]</code>, target =&nbsp;<code>8</code>,\n",
    "<strong>输出:</strong>\n",
    "[\n",
    "[1,1,6],\n",
    "[1,2,5],\n",
    "[1,7],\n",
    "[2,6]\n",
    "]</pre>\n",
    "\n",
    "<p><strong>示例&nbsp;2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> candidates =&nbsp;[2,5,2,1,2], target =&nbsp;5,\n",
    "<strong>输出:</strong>\n",
    "[\n",
    "[1,2,2],\n",
    "[5]\n",
    "]</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;=&nbsp;candidates.length &lt;= 100</code></li>\n",
    "\t<li><code>1 &lt;=&nbsp;candidates[i] &lt;= 50</code></li>\n",
    "\t<li><code>1 &lt;= target &lt;= 30</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [combination-sum-ii](https://leetcode.cn/problems/combination-sum-ii/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [combination-sum-ii](https://leetcode.cn/problems/combination-sum-ii/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[10,1,2,7,6,1,5]\\n8', '[2,5,2,1,2]\\n5']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        candidates.sort()\n",
    "        res = []\n",
    "        self.back(res, [], candidates, target, 0)\n",
    "        return res\n",
    "\n",
    "    def back(self, res, tmp, nums, k, j):\n",
    "        if k == 0:\n",
    "            res.append(tmp)\n",
    "            return\n",
    "        if k < 0 or j == len(nums):\n",
    "            return\n",
    "        for i in range(j, len(nums)):\n",
    "            if i == j or nums[i] != nums[i-1]:\n",
    "                self.back(res, tmp+[nums[i]], nums, k-nums[i], i+1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.track = []\n",
    "        self.rst = []\n",
    "        self.summ = 0\n",
    "\n",
    "    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        candidates.sort()\n",
    "        self.backtrack(candidates, 0, target)\n",
    "        return self.rst\n",
    "    \n",
    "    def backtrack(self, nums, start, target):\n",
    "        if self.summ == target:\n",
    "            self.rst.append(self.track[:])\n",
    "            return \n",
    "        if self.summ > target:\n",
    "            return\n",
    "\n",
    "        for i in range(start, len(nums)):\n",
    "            if i > start and nums[i] == nums[i-1]:\n",
    "                continue\n",
    "            self.summ += nums[i]\n",
    "            self.track.append(nums[i])\n",
    "            self.backtrack(nums, i + 1, target)\n",
    "            self.summ -= nums[i]\n",
    "            self.track.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.path = []\n",
    "        self.res = []\n",
    "    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        self.n = len(candidates)\n",
    "        candidates.sort()\n",
    "        self.used = [False] * self.n\n",
    "        self.dfs(0,candidates,target)\n",
    "        return self.res\n",
    "    def dfs(self, index, candidates, target):\n",
    "        if target == 0:\n",
    "            self.res.append(self.path[:])\n",
    "        for i in range(index, self.n):\n",
    "            if candidates[i] > target:\n",
    "                break\n",
    "            if (i > 0 and candidates[i] == candidates[i-1] and not self.used[i-1]) or self.used[i]:\n",
    "                continue\n",
    "            self.path.append(candidates[i])\n",
    "            self.used[i] = True\n",
    "            self.dfs(i+1,candidates,target-candidates[i])\n",
    "            self.path.pop()\n",
    "            self.used[i] = False\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res = []\n",
    "        self.track = []\n",
    "        self.tracksum = 0\n",
    "    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        candidates.sort()\n",
    "        self.backtrack(candidates, 0, target)\n",
    "        return self.res\n",
    "    def backtrack(self, nums, start, target):\n",
    "        if self.tracksum == target:\n",
    "            self.res.append(self.track.copy())\n",
    "            return\n",
    "        if self.tracksum > target:\n",
    "            return\n",
    "        for i in range(start, len(nums)):\n",
    "            if i > start and nums[i] == nums[i - 1]:\n",
    "                continue\n",
    "            self.track.append(nums[i])\n",
    "            self.tracksum += nums[i]\n",
    "            self. backtrack(nums, i + 1, target)\n",
    "            self.tracksum -= nums[i]\n",
    "            self.track.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        def dfs(index,used,target,res,ans):\n",
    "            if target==0:\n",
    "                ans.append(res[:])\n",
    "                return\n",
    "            for i in range(index,len(candidates)):\n",
    "                if used[i] or (candidates[i]==candidates[i-1] and not used[i-1] and i-1>=0):\n",
    "                    continue\n",
    "                if candidates[i]<=target and not used[i]:\n",
    "                    used[i]=True\n",
    "                    res.append(candidates[i])\n",
    "                    dfs(i,used,target-candidates[i],res,ans)\n",
    "                    res.pop()\n",
    "                    used[i]=False\n",
    "        ans=list()\n",
    "        used=[False]*len(candidates)\n",
    "        candidates.sort(reverse=False)\n",
    "        dfs(0,used,target,[],ans)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        arr = []\n",
    "        candidates.sort()\n",
    "        def tracrBack(i, path, target):\n",
    "            if target<0:\n",
    "                return\n",
    "            if target == 0:\n",
    "                arr.append(path[:])\n",
    "                return\n",
    "            for idx in range(i, len(candidates)):\n",
    "                if idx > i and candidates[idx] == candidates[idx-1]:\n",
    "                    continue\n",
    "                path.append(candidates[idx])\n",
    "                tracrBack(idx+1, path, target-candidates[idx])\n",
    "                path.pop()\n",
    "        tracrBack(0, [], target)\n",
    "        return arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        self.res = []\n",
    "        self.track = []\n",
    "        self.track_sum = 0\n",
    "        candidates.sort()\n",
    "        self.backtrack(candidates, target, 0)\n",
    "        return self.res\n",
    "\n",
    "    def backtrack(self, candidates, target, start):\n",
    "        if self.track_sum == target:\n",
    "            self.res.append(self.track[:])\n",
    "            return\n",
    "        \n",
    "        if self.track_sum > target:\n",
    "            return \n",
    "        \n",
    "        for i in range(start, len(candidates)):\n",
    "            # 剪枝\n",
    "            if i > start and candidates[i] == candidates[i-1]:\n",
    "                continue\n",
    "\n",
    "            self.track.append(candidates[i])\n",
    "            self.track_sum += candidates[i]\n",
    "\n",
    "            self.backtrack(candidates, target, i+1)\n",
    "\n",
    "            self.track.pop()\n",
    "            self.track_sum -= candidates[i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        res=[]\n",
    "        path=[]\n",
    "        sumval=0\n",
    "        candidates.sort()\n",
    "        n=len(candidates)\n",
    "        def backtrack(res,path,start,n,sumval):\n",
    "            if sumval==target:\n",
    "                res.append(path[:])\n",
    "            if sumval>target:\n",
    "                return\n",
    "            for i in range (start,n):\n",
    "                if i>start and candidates[i]==candidates[i-1]:\n",
    "                    continue\n",
    "                path.append(candidates[i])\n",
    "                sumval+=candidates[i]\n",
    "                backtrack(res,path,i+1,n,sumval)\n",
    "                path.pop()\n",
    "                sumval-=candidates[i]\n",
    "        backtrack(res,path,0,n,sumval)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        ans = []\n",
    "        path = []\n",
    "        n = len(candidates)\n",
    "        candidates.sort()\n",
    "\n",
    "        vis = [False] * n\n",
    "        def dfs(start, target):\n",
    "            if target==0:\n",
    "                ans.append(path[:])\n",
    "                return\n",
    "            for i in range(start, n):\n",
    "                if i>0 and candidates[i] == candidates[i-1] and not vis[i-1]:\n",
    "                    continue\n",
    "                if target - candidates[i] >= 0:\n",
    "                    path.append(candidates[i])\n",
    "                    vis[i] = True\n",
    "                    dfs(i+1, target - candidates[i])\n",
    "                    path.pop()\n",
    "                    vis[i] = False\n",
    "                else:\n",
    "                    return \n",
    "        dfs(0, target)\n",
    "        return ans            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        n=len(candidates)\n",
    "        candidates.sort()\n",
    "        res=[]\n",
    "        def dfs(idx,count,path):\n",
    "            if idx>n or target<count:\n",
    "                return \n",
    "            if count==target:\n",
    "                res.append(path[:])\n",
    "            dp=[]\n",
    "            for i in range(idx,n):\n",
    "                if candidates[i] not in dp:\n",
    "                    dp.append(candidates[i])\n",
    "                    path.append(candidates[i])\n",
    "                    dfs(i+1,candidates[i]+count,path)\n",
    "                    path.pop()\n",
    "    \n",
    "        dfs(0,0,[])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        res = []\n",
    "        tmp = []\n",
    "        candidates.sort()\n",
    "\n",
    "        def dfs(i, curr_sum):\n",
    "            if curr_sum == target:\n",
    "                res.append(list(tmp))\n",
    "                return\n",
    "\n",
    "            if curr_sum > target or i == len(candidates):\n",
    "                return\n",
    "\n",
    "            j = i\n",
    "            cnt = 0\n",
    "            while j < len(candidates) and candidates[j] == candidates[i]:\n",
    "                j += 1\n",
    "                if curr_sum + candidates[i] <= target:\n",
    "                    tmp.append(candidates[i])\n",
    "                    cnt += 1\n",
    "                    curr_sum += candidates[i]\n",
    "        \n",
    "            dfs(j, curr_sum)\n",
    "            for t in range(cnt):\n",
    "                curr_sum -= candidates[i]\n",
    "                tmp.pop()\n",
    "                dfs(j, curr_sum)\n",
    "\n",
    "        dfs(0, 0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "\n",
    "        def recur(i, tmp, s):\n",
    "            if s == target:\n",
    "                res.append(tmp)\n",
    "                return\n",
    "            if s > target:\n",
    "                return\n",
    "            for j in range(i, n):\n",
    "                if j > i and candidates[j] == candidates[j-1]:\n",
    "                    continue\n",
    "                recur(j+1, tmp+[candidates[j]], s+candidates[j])\n",
    "        \n",
    "        res = []\n",
    "        n = len(candidates)\n",
    "        candidates.sort()\n",
    "        recur(0, [], 0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        return self.search(\n",
    "            sorted(candidates),\n",
    "            [False] * len(candidates),\n",
    "            0,\n",
    "            target,\n",
    "        )\n",
    "\n",
    "    def search(\n",
    "        self,\n",
    "        candidates: List[int],\n",
    "        used: List[bool],\n",
    "        start_pos: int,\n",
    "        target: int,\n",
    "    ) -> List[List[int]]:\n",
    "        combinations = []\n",
    "        for i in range(start_pos, len(candidates)):\n",
    "            if used[i] or candidates[i] > target:\n",
    "                continue\n",
    "            if (i > 0 and candidates[i] == candidates[i - 1]\n",
    "                    and not used[i - 1]):\n",
    "                continue\n",
    "            used[i] = True\n",
    "            if candidates[i] == target:\n",
    "                combinations.append(\n",
    "                    [candidates[i] for i in range(len(candidates)) if used[i]])\n",
    "            else:\n",
    "                combinations += self.search(\n",
    "                    candidates,\n",
    "                    used,\n",
    "                    i,\n",
    "                    target - candidates[i],\n",
    "                )\n",
    "            used[i] = False\n",
    "        return combinations"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        candidates.sort()\n",
    "        path = []\n",
    "        res = []\n",
    "        vis = [False] * len(candidates)\n",
    "        def backwards(start, sum, candidates):\n",
    "            if sum == target:\n",
    "                res.append(path[:])\n",
    "                return\n",
    "            for i in range(start, len(candidates)):\n",
    "                if i > 0 and candidates[i] == candidates[i-1] and not vis[i - 1]:\n",
    "                    continue\n",
    "                sum += candidates[i]\n",
    "                if sum <= target:\n",
    "                    path.append(candidates[i])\n",
    "                    vis[i] = True\n",
    "                    backwards(i+1, sum, candidates)\n",
    "                    path.pop()\n",
    "                    sum -= candidates[i]\n",
    "                    vis[i] = False\n",
    "                else:\n",
    "                    return\n",
    "        backwards(0, 0, candidates)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        self.res = []\n",
    "        self.track = []\n",
    "        self.track_sum = 0\n",
    "        candidates.sort()\n",
    "        self.backtrack(candidates, target, 0)\n",
    "        return self.res\n",
    "\n",
    "    def backtrack(self, candidates, target, start):\n",
    "        if self.track_sum == target:\n",
    "            self.res.append(self.track[:])\n",
    "            return\n",
    "        \n",
    "        if self.track_sum > target:\n",
    "            return \n",
    "        \n",
    "        for i in range(start, len(candidates)):\n",
    "            if i > start and candidates[i] == candidates[i-1]:\n",
    "                continue\n",
    "            self.track.append(candidates[i])\n",
    "            self.track_sum += candidates[i]\n",
    "\n",
    "            self.backtrack(candidates, target, i+1)\n",
    "\n",
    "            self.track.pop()\n",
    "            self.track_sum -= candidates[i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def backtrack(self,starindex,target,candidate,path,res):\n",
    "        if sum(path)==target:\n",
    "            if path not in res:\n",
    "                res.append(path[:])\n",
    "            return\n",
    "        \n",
    "        for i in range(starindex,len(candidate)):\n",
    "            if i > starindex and candidate[i] == candidate[i - 1]:  # 处理重复的情况，避免重复组合\n",
    "                continue\n",
    "\n",
    "\n",
    "            if sum(path)>target:\n",
    "                break\n",
    "            path.append(candidate[i])\n",
    "            \n",
    "            \n",
    "            self.backtrack(i+1,target,candidate,path,res)\n",
    "            path.pop()\n",
    "        return res\n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        candidates.sort()\n",
    "    \n",
    "        res=self.backtrack(0,target,candidates,[],[])\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        ans = []\n",
    "        combine = []\n",
    "        freq = sorted(collections.Counter(candidates).items())\n",
    "        n = len(freq)\n",
    "        \n",
    "        def dfs(target: int, idx: int) -> None:\n",
    "            nonlocal combine\n",
    "\n",
    "            if target == 0:\n",
    "                ans.append(combine[:])\n",
    "                return\n",
    "\n",
    "            if idx == n or target < freq[idx][0]:\n",
    "                return\n",
    "            \n",
    "            dfs(target, idx + 1)\n",
    "\n",
    "            most = min(freq[idx][1], target // freq[idx][0])\n",
    "            for i in range(1, most+1):\n",
    "                combine.append(freq[idx][0])\n",
    "                dfs(target - i * freq[idx][0], idx + 1)\n",
    "            combine = combine[:-most]\n",
    "\n",
    "        dfs(target, 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        candidates.sort()\n",
    "        self.res = []\n",
    "        path = []\n",
    "        \n",
    "        vis = [False] * len(candidates)\n",
    "\n",
    "        def dfs(s,cur):\n",
    "            if cur == target:\n",
    "                self.res.append(path[:])\n",
    "                return\n",
    "            \n",
    "            for idx in range(s,len(candidates)):\n",
    "                if idx > 0 and candidates[idx] == candidates[idx - 1] and not vis[idx - 1]:\n",
    "                    continue\n",
    "                \n",
    "                cur += candidates[idx]\n",
    "                \n",
    "                if cur <= target:\n",
    "                    path.append(candidates[idx])\n",
    "                    vis[idx] = True\n",
    "                    dfs(idx + 1,cur)\n",
    "                    path.pop()\n",
    "                    cur -= candidates[idx]\n",
    "                    vis[idx] = False\n",
    "                else:\n",
    "                    return\n",
    "        \n",
    "        dfs(0,0)\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        self.res  = []\n",
    "        track = []\n",
    "        candidates = sorted(candidates)\n",
    "        numsum =0\n",
    "        start = 0\n",
    "        used = [False]*len(candidates)\n",
    "        self.trackback(candidates, target, track, numsum,start,used)\n",
    "        return self.res\n",
    "\n",
    "    def trackback(self, candidates,target,track,numsum,start,used):\n",
    "        if numsum == target:\n",
    "            self.res.append(track[:])\n",
    "            return self.res\n",
    "        if numsum > target:\n",
    "            return\n",
    "        for i in range(start, len(candidates)):\n",
    "            if candidates[i]==candidates[i-1] and i>start and not used[i-1]:\n",
    "                continue\n",
    "            if not used[i]:\n",
    "                used[i] = True\n",
    "                track.append(candidates[i])\n",
    "                numsum+=candidates[i]\n",
    "                self.trackback(candidates, target, track, numsum, i, used)\n",
    "                used[i] = False\n",
    "                track.pop()\n",
    "                numsum-=candidates[i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "\n",
    "        candidates.sort()\n",
    "        ans = []\n",
    "        path = []\n",
    "\n",
    "        def dfs(start: int, s: int):\n",
    "            if s == target:\n",
    "                ans.append(path[:])\n",
    "                return\n",
    "            if s > target:\n",
    "                return\n",
    "            \n",
    "            for i in range(start, len(candidates)):\n",
    "                if i > start and candidates[i] == candidates[i - 1]:\n",
    "                    continue\n",
    "                path.append(candidates[i])\n",
    "                dfs(i + 1, s + candidates[i])\n",
    "                path.pop()\n",
    "        \n",
    "\n",
    "        dfs(0, 0)\n",
    "        return ans   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.track = []\n",
    "        self.res = []\n",
    "    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        candidates.sort()\n",
    "        self.backtrack(candidates,0,target)\n",
    "        return self.res\n",
    "    def backtrack(self,nums,start,target):\n",
    "        # base case\n",
    "        if sum(self.track)==target:\n",
    "            self.res.append(self.track[:])\n",
    "            return \n",
    "        # base case\n",
    "        # 关键一步 大于目标值的路径没必要继续遍历\n",
    "        if sum(self.track) > target:\n",
    "            return\n",
    "\n",
    "        for i in range(start,len(nums)):\n",
    "            if i>start and nums[i-1]==nums[i]:\n",
    "                continue\n",
    "            self.track.append(nums[i])\n",
    "            self.backtrack(nums,i+1,target)\n",
    "            self.track.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        ans = []\n",
    "        numbers = collections.Counter(candidates)\n",
    "        unique = sorted(list(numbers.keys()))\n",
    "        n = len(unique)\n",
    "\n",
    "        # 回溯三要素：\n",
    "        # 1）结束条件：找到的组合之和等于target，或者大于target(candidates[i]都大于0)\n",
    "        # 2）选择列表：进入下一层递归，从start+1开始寻找\n",
    "        # 3）搜索路径：\n",
    "        def backtrack(start, num, path):\n",
    "            if num == 0:\n",
    "                ans.append(path)\n",
    "                return\n",
    "            if num < 0:\n",
    "                return\n",
    "            for i in range(start, n):\n",
    "                for loop in range(1, numbers[unique[i]] + 1):\n",
    "                    backtrack(i + 1, num - unique[i] * loop, path + [unique[i]] * loop)\n",
    "\n",
    "        backtrack(0, target, [])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum2(self, candidates, target: int):\n",
    "        ans=[]\n",
    "        path=[]\n",
    "        candidates.sort()\n",
    "        def dfs(i):\n",
    "            if sum(path)==target and path not in ans:\n",
    "                ans.append(path.copy())\n",
    "                return\n",
    "            elif sum(path)>target:\n",
    "                return\n",
    "            else:\n",
    "                for j in range(i,len(candidates)):\n",
    "                    if j>i and candidates[j]==candidates[j-1]:\n",
    "                        continue\n",
    "                    #path.append(candidates[i])错误写法，动态变换的索引是j\n",
    "                    path.append(candidates[j])\n",
    "                    dfs(j+1)\n",
    "                    path.pop()\n",
    "        dfs(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        res = []\n",
    "        candidates.sort() # 排序很灵性, 保证相同元素聚集\n",
    "        def backtrack(idx, path, candidate, target):\n",
    "            if target < 0: return\n",
    "            if target == 0:\n",
    "                res.append(path.copy())\n",
    "                return\n",
    "            for i in range(idx, len(candidates)):\n",
    "                if i > idx and candidates[i - 1] == candidates[i]: # 这个去重逻辑很重要, 需要判断 i -1 和 i 的值, 这样保证第一个重复元素可以正常回溯, 之后的都被剪, 如果判断 i + 1 和 i, 则从最后一个重复元素开始操作, 会丢失前面的重复元素           \n",
    "                    continue\n",
    "                path.append(candidates[i])\n",
    "                backtrack(i + 1, path, candidates[i], target - candidates[i])\n",
    "                path.pop()\n",
    "        \n",
    "        backtrack(0, [], -1, target)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        n = len(candidates)\n",
    "        candidates.sort()\n",
    "        ans = []\n",
    "\n",
    "        def backtracking(cur, idx, total):\n",
    "            if total == target:\n",
    "                nonlocal ans\n",
    "                ans.append(cur.copy())\n",
    "            if total > target or idx == n:\n",
    "                return \n",
    "            \n",
    "            for i in range(idx, n):\n",
    "                if i > idx and candidates[i] == candidates[i-1]:\n",
    "                    continue\n",
    "                cur.append(candidates[i])\n",
    "                backtracking(cur, i+1, total+candidates[i])\n",
    "                cur.pop(-1)\n",
    "        \n",
    "        last = 0\n",
    "        for i in range(n):\n",
    "            if candidates[i] != last:\n",
    "                backtracking([candidates[i]], i+1, total=candidates[i])\n",
    "                last = candidates[i]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        path = []\n",
    "        res = []\n",
    "        candidates = sorted(candidates)\n",
    "        def backtracking(startIndex, candidates, target):\n",
    "            if target == 0:\n",
    "                res.append(path.copy())\n",
    "                return\n",
    "            if target < 0:\n",
    "                return\n",
    "            for i in range(startIndex, len(candidates)):\n",
    "                if i != startIndex and candidates[i] == candidates[i-1]:\n",
    "                    continue\n",
    "                target -= candidates[i]\n",
    "                path.append(candidates[i])\n",
    "                backtracking(i+1, candidates, target)\n",
    "                path.pop()\n",
    "                target += candidates[i]\n",
    "        backtracking(0, candidates, target)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        candidates.sort()\n",
    "        n = len(candidates)\n",
    "        path = []\n",
    "        res = []\n",
    "        def dfs(depth):\n",
    "            if sum(path) == target:\n",
    "                res.append(path[:])\n",
    "                return\n",
    "            for i in range(depth, n):\n",
    "                if i > depth and candidates[i] == candidates[i-1]:\n",
    "                    continue\n",
    "                path.append(candidates[i])\n",
    "                if sum(path) > target:\n",
    "                    path.pop()\n",
    "                    return\n",
    "                dfs(i+1)\n",
    "                path.pop()\n",
    "        dfs(0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        path = []\n",
    "        ans = []\n",
    "        sums = 0\n",
    "        candidates.sort()\n",
    "        n = len(candidates)\n",
    "        b = False \n",
    "        def dfs(i:int):\n",
    "            nonlocal sums\n",
    "            nonlocal b\n",
    "            if sums > target:\n",
    "                return\n",
    "            elif sums == target:\n",
    "                ans.append(path.copy())\n",
    "                return \n",
    "            for j in range(i,n):\n",
    "                if b and j > 0 and candidates[j] == candidates[j-1]:\n",
    "                    continue\n",
    "                b = False\n",
    "                path.append(candidates[j])\n",
    "                sums += candidates[j]\n",
    "                dfs(j+1)\n",
    "                if sums >= target:\n",
    "                    sums -= path.pop()\n",
    "                    b = True\n",
    "                    return \n",
    "                sums -= path.pop()\n",
    "                b = True\n",
    "        dfs(0)\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "\n",
    "\n",
    "        path = [] \n",
    "        res = [] \n",
    "\n",
    "        candidates.sort() \n",
    "\n",
    "        vis = [False for i in range(len(candidates))]\n",
    "\n",
    "        def backward(start,sum,candidates):\n",
    "            # 返回条件 1、相等  2、 sum> target 没有＋的必要了\n",
    "\n",
    "\n",
    "            if sum == target:\n",
    "                res.append(path[:])\n",
    "                return \n",
    "            for i in range(start,len(candidates)):\n",
    "                #   避免 1 ，1 这种反复计算，但是保留 1+1的情况\n",
    "                if i > 0  and candidates[i] == candidates[i-1] and not vis[i-1]:\n",
    "\n",
    "                    continue \n",
    "\n",
    "                sum += candidates[i]\n",
    "                if sum<=target:\n",
    "                    vis[i] = True \n",
    "                    path.append(candidates[i])\n",
    "\n",
    "                    backward(i+1,sum,candidates)\n",
    "\n",
    "                    path.pop() \n",
    "                    \n",
    "                    vis[i] = False\n",
    "                    sum-=candidates[i]\n",
    "                else:\n",
    "                    return \n",
    "        backward(0,0,candidates)\n",
    "        return res\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        # load = []\n",
    "        n = len(candidates)\n",
    "        nums = candidates\n",
    "        nums.sort()\n",
    "        res = []\n",
    "        def dfs(i, load, tar):\n",
    "            # nonlocal load\n",
    "            if tar == 0:\n",
    "                # print(load)\n",
    "                res.append(load)\n",
    "                return\n",
    "            for j in range(i, n):\n",
    "                if j > i and nums[j] == nums[j - 1]:\n",
    "                    continue\n",
    "                if tar - nums[j] < 0:\n",
    "                    break\n",
    "                # load.append(nums[j])\n",
    "                dfs(j + 1, load + [nums[j]], tar - nums[j])\n",
    "                # load.pop()\n",
    "        dfs(0, [], target)\n",
    "        return res\n",
    "        \n",
    "#         dp = []\n",
    "#         # dp = [target for i in range(len(candidates))]\n",
    "#         def traverse(index, load, sums):\n",
    "#             # print(load)\n",
    "#             if index >= len(candidates):\n",
    "#                 return\n",
    "#             if sums > target:\n",
    "#                 return\n",
    "#             if sums == target:\n",
    "#                 # if load == [1, 2, 5]:\n",
    "#                 print(load)\n",
    "#                 if load not in dp:\n",
    "#                     dp.append(load)\n",
    "#                 return\n",
    "#             tmp1 = copy.deepcopy(load)\n",
    "#             tmp1.append(candidates[index])\n",
    "#             tmp2 = copy.deepcopy(load)\n",
    "#             traverse(index+1, tmp1, sums+candidates[index])\n",
    "            \n",
    "#             traverse(index+1, tmp2, sums)\n",
    "#             return\n",
    "\n",
    "#         for index in range(len(candidates)):\n",
    "#             load = []\n",
    "#             sums = 0\n",
    "#             final = traverse(index, load, sums)\n",
    "#             # if final not in memo:\n",
    "#             #     memo.append(final)\n",
    "#             # # return memo\n",
    "#             # print(final)\n",
    "#         print(dp)\n",
    "#         return dp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        candidates.sort()\n",
    "        res,path,start_index = [],[],0\n",
    "        self.backtracking(candidates,res,path,target,start_index)\n",
    "        return res\n",
    "\n",
    "    #确定递归函数参数\n",
    "    def backtracking(self,candidates,res,path,target,start_index):\n",
    "        if target < 0:\n",
    "            return\n",
    "        if target == 0:\n",
    "            res.append(path[:])\n",
    "            return\n",
    "        for i in range(start_index,len(candidates)):\n",
    "            if i > start_index and candidates[i] == candidates[i - 1]:\n",
    "                continue\n",
    "            path.append(candidates[i])\n",
    "            target -= candidates[i]\n",
    "            self.backtracking(candidates,res,path,target,i+1)\n",
    "            target += candidates[i]\n",
    "            path.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        def dfs(pos: int, rest: int):\n",
    "            nonlocal sequence\n",
    "            if rest == 0:\n",
    "                ans.append(sequence[:])\n",
    "                return\n",
    "            if pos == len(freq) or rest < freq[pos][0]:\n",
    "                return\n",
    "            \n",
    "            dfs(pos + 1, rest)\n",
    "\n",
    "            most = min(rest // freq[pos][0], freq[pos][1])\n",
    "            for i in range(1, most + 1):\n",
    "                sequence.append(freq[pos][0])\n",
    "                dfs(pos + 1, rest - i * freq[pos][0])\n",
    "            sequence = sequence[:-most]\n",
    "        \n",
    "        freq = sorted(collections.Counter(candidates).items())\n",
    "        ans = list()\n",
    "        sequence = list()\n",
    "        dfs(0, target)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:\r\n",
    "        candidates = sorted(candidates)\r\n",
    "        res = []\r\n",
    "        for ind in range(len(candidates)):\r\n",
    "            if ind > 0 and candidates[ind] == candidates[ind-1]:\r\n",
    "                continue\r\n",
    "            v = candidates[ind]\r\n",
    "            if v > target:\r\n",
    "                continue\r\n",
    "            elif v == target:\r\n",
    "                res.append([v])\r\n",
    "            elif v < target:\r\n",
    "                tt = self.combinationSum2(candidates[ind+1:], target-v)\r\n",
    "                if tt:\r\n",
    "                    res += [[v]+ctt for ctt in tt]\r\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        \"\"\"\n",
    "        与组合总和I不同，此题candidates中的每个数字在每个组合中只能使用一次。\n",
    "        \"\"\"\n",
    "        freq = sorted(collections.Counter(candidates).items())\n",
    "        n = len(freq)\n",
    "\n",
    "        def dfs(target, start):\n",
    "            if start >= n or target < freq[start][0]:\n",
    "                return []\n",
    "            \n",
    "            res = []\n",
    "\n",
    "            most = min(target // freq[start][0], freq[start][1])\n",
    "            \n",
    "            if target-most*freq[start][0] == 0:\n",
    "                res.append([freq[start][0]]*most)\n",
    "                most -= 1\n",
    "\n",
    "            for j in range(most, -1, -1):\n",
    "                for r in dfs(target-j*freq[start][0], start+1):\n",
    "                    res.append([freq[start][0]]*j+r)\n",
    "\n",
    "            return res\n",
    "\n",
    "        return dfs(target, 0) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        if not candidates:\n",
    "            return []\n",
    "\n",
    "        self.target = target\n",
    "        candidates.sort()\n",
    "        self.track = []\n",
    "        self.res = []\n",
    "        self.bt(candidates, 0, 0)\n",
    "        return self.res\n",
    "\n",
    "    def bt(self, candidates, start, sum):\n",
    "        if sum == self.target:\n",
    "            self.res.append(self.track[:])\n",
    "            return\n",
    "        if start == len(candidates):\n",
    "            return\n",
    "        for i in range(start, len(candidates)):\n",
    "            if i > start and candidates[i] == candidates[i-1]:\n",
    "                continue\n",
    "            item = candidates[i]\n",
    "            if sum + item > self.target:\n",
    "                break\n",
    "            self.track.append(item)\n",
    "            sum += item\n",
    "            self.bt(candidates, i+1, sum)\n",
    "            sum -= item\n",
    "            self.track.pop() "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        def dfs(pos: int, rest: int):\n",
    "            nonlocal sequence\n",
    "            if rest == 0:\n",
    "                ans.append(sequence[:])\n",
    "                return\n",
    "            if pos == len(freq) or rest < freq[pos][0]:\n",
    "                return\n",
    "            \n",
    "            dfs(pos + 1, rest)\n",
    "\n",
    "            most = min(rest // freq[pos][0], freq[pos][1])\n",
    "            for i in range(1, most + 1):\n",
    "                sequence.append(freq[pos][0])\n",
    "                dfs(pos + 1, rest - i * freq[pos][0])\n",
    "            sequence = sequence[:-most]\n",
    "        \n",
    "        freq = sorted(collections.Counter(candidates).items())\n",
    "        ans = list()\n",
    "        sequence = list()\n",
    "        dfs(0, target)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        res = list()\n",
    "        path = list()\n",
    "        def dfs(total, index):\n",
    "            if total == target:\n",
    "                res.append(path[:])\n",
    "                return\n",
    "            if total > target:\n",
    "                return\n",
    "            for i in range(index, len(candidates)):\n",
    "                if i > index and candidates[i] == candidates[i-1]:\n",
    "                    continue\n",
    "                if candidates[i] + total > target:\n",
    "                    break\n",
    "                path.append(candidates[i])\n",
    "                total += candidates[i]\n",
    "                dfs(total, i+1)\n",
    "                path.pop()\n",
    "                total -= candidates[i]\n",
    "        candidates.sort()\n",
    "        dfs(0, 0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        n=len(candidates)\n",
    "        ans=[]\n",
    "        candidates.sort()\n",
    "        def dfs(idx,cnt,path):\n",
    "            if cnt==target:\n",
    "                ans.append(path[:])\n",
    "                return \n",
    "            if idx>=n and cnt>target:\n",
    "                return\n",
    "            for i in range(idx,n):\n",
    "                #同层去重\n",
    "                if i>idx and candidates[i]==candidates[i-1]:\n",
    "                    continue\n",
    "                if cnt+candidates[i]<=target:\n",
    "                    path.append(candidates[i])\n",
    "                    dfs(i+1,cnt+candidates[i],path)\n",
    "                    path.pop()\n",
    "        dfs(0,0,[])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        candidates.sort()\n",
    "        ans = []\n",
    "        def dfs(nums, pos, num_target, path):\n",
    "            if num_target == 0:\n",
    "                ans.append(path[:])\n",
    "                return\n",
    "            if pos >= len(nums):\n",
    "                return\n",
    "\n",
    "            for i in range(pos, len(nums)):\n",
    "                if i > pos and nums[i-1] == nums[i]:\n",
    "                    continue\n",
    "                if nums[i] <= num_target:\n",
    "                    path.append(nums[i])\n",
    "                    dfs(nums, i+1,num_target - nums[i], path)\n",
    "                    path.pop()\n",
    "\n",
    "\n",
    "        dfs(candidates, 0, target, [])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        path = []\n",
    "        ans = []\n",
    "        sums = 0\n",
    "        candidates.sort()\n",
    "        n = len(candidates)\n",
    "        b = False \n",
    "        def dfs(i:int):\n",
    "            nonlocal sums\n",
    "            nonlocal b\n",
    "            if sums > target:\n",
    "                return\n",
    "            elif sums == target:\n",
    "                ans.append(path.copy())\n",
    "                return \n",
    "            for j in range(i,n):\n",
    "                if b and j > 0 and candidates[j] == candidates[j-1]:\n",
    "                    continue\n",
    "                b = False\n",
    "                path.append(candidates[j])\n",
    "                sums += candidates[j]\n",
    "                dfs(j+1)\n",
    "                if sums >= target:\n",
    "                    sums -= path.pop()\n",
    "                    # b = True\n",
    "                    return \n",
    "                sums -= path.pop()\n",
    "                b = True\n",
    "        dfs(0)\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        candidates.sort()\n",
    "        result=[]\n",
    "\n",
    "        def backtrack(start,sub_result,all_sum):\n",
    "            if all_sum==target:\n",
    "                result.append(sub_result[:])\n",
    "                return\n",
    "            if all_sum>target:\n",
    "                return\n",
    "            \n",
    "            for i in range(start,len(candidates)):\n",
    "                if i>start and candidates[i]==candidates[i-1]:\n",
    "                    continue\n",
    "                sub_result.append(candidates[i])\n",
    "                all_sum+=candidates[i]\n",
    "                backtrack(i+1,sub_result,all_sum)\n",
    "                sub_result.pop()\n",
    "                all_sum-=candidates[i]\n",
    "        backtrack(0,[],0)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def process(self, sum, startidx):\n",
    "        if sum == self.target:\n",
    "            self.result.append(self.tmp[:])\n",
    "            return\n",
    "        if sum > self.target:\n",
    "            return\n",
    "\n",
    "        for i in range(startidx, self.length):\n",
    "            if (i>0) and (self.candidates[i] == self.candidates[i-1]) and (not self.used[i-1]):\n",
    "                continue\n",
    "            self.tmp.append(self.candidates[i])\n",
    "            self.used[i] = True\n",
    "            self.process(sum+self.candidates[i], i+1)\n",
    "            self.tmp.pop()\n",
    "            self.used[i] = False\n",
    "    \n",
    "    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        self.tmp = []\n",
    "        self.result = []\n",
    "        self.used = []\n",
    "        self.length = len(candidates)\n",
    "        self.target = target\n",
    "        self.candidates = candidates\n",
    "        self.candidates.sort()\n",
    "        print(self.candidates)\n",
    "        for i in range(self.length):\n",
    "            self.used.append(False)\n",
    "\n",
    "        self.process(0, 0)\n",
    "\n",
    "        return self.result\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from copy import copy\n",
    "class Solution:\n",
    "    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        m = sorted(list(Counter(candidates).items()))\n",
    "        print(m)\n",
    "        ans, n = [], len(m)\n",
    "\n",
    "        def dsf(i, pre, t):\n",
    "            nonlocal ans\n",
    "            if pre == 0:\n",
    "                ans.append(t)\n",
    "                return\n",
    "            \n",
    "            if i >= n or pre < 0:\n",
    "                return\n",
    "            \n",
    "            for j in range(m[i][1] + 1):\n",
    "                np = pre - j * m[i][0]\n",
    "                t_ = copy(t) + [m[i][0]] * j\n",
    "                dsf(i + 1, np, t_)\n",
    "            return\n",
    "\n",
    "        dsf(0, target, [])\n",
    "        return ans\n",
    "            \n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        \n",
    "        if len(candidates) == 0:\n",
    "            return []\n",
    "        nums = sorted(candidates)\n",
    "        \n",
    "        path = []\n",
    "        reslist = []\n",
    "        used = [False] * len(nums)\n",
    "        def backtracking(startindex, cursum):\n",
    "            \n",
    "            if cursum == target:\n",
    "                reslist.append(path[:])\n",
    "                return\n",
    "            if startindex >= len(nums)  or cursum > target:\n",
    "                return\n",
    "\n",
    "            for i in range(startindex, len(nums)):\n",
    "                if i - 1 >= 0 and nums[i] == nums[i - 1] and used[i - 1] == False:\n",
    "                    continue\n",
    "                path.append(nums[i])\n",
    "                cursum += nums[i]\n",
    "                used[i] = True\n",
    "                backtracking(i + 1, cursum)\n",
    "                path.pop()\n",
    "                cursum -= nums[i]\n",
    "                used[i] = False\n",
    "            return\n",
    "        \n",
    "        backtracking(0, 0)\n",
    "        return reslist"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def process(self, sum, startidx):\n",
    "        if sum == self.target:\n",
    "            self.result.append(self.tmp[:])\n",
    "            return\n",
    "        if sum > self.target:\n",
    "            return\n",
    "\n",
    "        for i in range(startidx, self.length):\n",
    "            if (i>0) and (self.candidates[i] == self.candidates[i-1]) and (not self.used[i-1]):\n",
    "                continue\n",
    "            self.tmp.append(self.candidates[i])\n",
    "            self.used[i] = True\n",
    "            self.process(sum+self.candidates[i], i+1)\n",
    "            self.tmp.pop()\n",
    "            self.used[i] = False\n",
    "    \n",
    "    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        self.tmp = []\n",
    "        self.result = []\n",
    "        self.used = []\n",
    "        self.length = len(candidates)\n",
    "        self.target = target\n",
    "        self.candidates = candidates\n",
    "        self.candidates.sort()\n",
    "        print(self.candidates)\n",
    "        for i in range(self.length):\n",
    "            self.used.append(False)\n",
    "\n",
    "        self.process(0, 0)\n",
    "\n",
    "        return self.result\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        result = []\n",
    "        tmp = []\n",
    "        # 优先排序优化\n",
    "        candidates.sort()\n",
    "        def dfs(ind, tmp, target):\n",
    "            # 首先你这个临界条件永远不会成立，所以相当于根本没设置临界\n",
    "            # if ind >= len(candidates):\n",
    "            #     return\n",
    "            # 为什么临界条件必须是下面这个而不是上面这个\n",
    "            if target<0:\n",
    "                return\n",
    "            if target == 0:\n",
    "                result.append(tmp.copy())\n",
    "                return\n",
    "            # dfs(ind+1, tmp, target)\n",
    "            for i in range(ind, len(candidates)):\n",
    "                if i!=ind and candidates[i] == candidates[i-1]:\n",
    "                    continue\n",
    "                \n",
    "                tmp.append(candidates[i])\n",
    "                dfs(i+1, tmp, target-candidates[i])\n",
    "                tmp.pop()\n",
    "            \n",
    "        dfs(0, tmp, target)\n",
    "        return result\n",
    "                \n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# https://labuladong.gitee.io/algo/di-ling-zh-bfe1b/hui-su-sua-56e11\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res = []\n",
    "        self.track = []\n",
    "\n",
    "    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        candidates.sort()\n",
    "        self.backtrack(candidates, target, 0)\n",
    "\n",
    "        return self.res\n",
    "\n",
    "    def backtrack(self, candidates, target, start):\n",
    "        # 终止条件做的事\n",
    "        if sum(self.track) == target:\n",
    "            self.res.append(self.track[:])\n",
    "            return\n",
    "        \n",
    "        # 剪枝。这一步也可以不写，但不写会比较耗时，写了就更节约时间\n",
    "        if sum(self.track) > target:\n",
    "            return\n",
    "\n",
    "        # 循环每一个选择\n",
    "        for i in range(start, len(candidates)):\n",
    "            # 剪枝\n",
    "            if i > start and candidates[i] == candidates[i-1]:\n",
    "                continue\n",
    "            # 做选择\n",
    "            self.track.append(candidates[i])\n",
    "            self.backtrack(candidates, target, i + 1)\n",
    "            self.track.pop()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        \n",
    "        if len(candidates) == 0:\n",
    "            return []\n",
    "        nums = sorted(candidates)\n",
    "        \n",
    "        path = []\n",
    "        reslist = []\n",
    "        used = [False] * len(nums)\n",
    "        def backtracking(startindex, cursum):\n",
    "            \n",
    "            if cursum == target:\n",
    "                reslist.append(path[:])\n",
    "                return\n",
    "            if cursum > target: # 注意要加cursum > target 的判断，否则会超时\n",
    "                return\n",
    "\n",
    "            for i in range(startindex, len(nums)):\n",
    "                if i - 1 >= 0 and nums[i] == nums[i - 1] and used[i - 1] == False:\n",
    "                    continue\n",
    "                path.append(nums[i])\n",
    "                cursum += nums[i]\n",
    "                used[i] = True\n",
    "                backtracking(i + 1, cursum)\n",
    "                path.pop()\n",
    "                cursum -= nums[i]\n",
    "                used[i] = False\n",
    "            return\n",
    "        \n",
    "        backtracking(0, 0)\n",
    "        return reslist"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "\n",
    "        def dfs(s,index,n,path):\n",
    "            if s==target:\n",
    "                res.append(path.copy())\n",
    "                return\n",
    "            if s>target:\n",
    "                return\n",
    "            for i in range(index,n):\n",
    "                if i>index and candidates[i] == candidates[i-1]:\n",
    "                    continue\n",
    "                path.append(candidates[i])\n",
    "                dfs(s+candidates[i],i+1,n,path)\n",
    "                path.pop()\n",
    "        res = []\n",
    "        candidates.sort()\n",
    "        dfs(0,0,len(candidates),[])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        def dfs(i, path, aim):\n",
    "            if aim == 0:\n",
    "                ans.append(path.copy())\n",
    "                return\n",
    "            for j in range(i, n):\n",
    "                if candidates[j] > aim:\n",
    "                    break\n",
    "                if j > i and candidates[j] == candidates[j - 1]:\n",
    "                    continue\n",
    "                path.append(candidates[j])\n",
    "                dfs(j + 1, path, aim - candidates[j])\n",
    "                path.pop()\n",
    "\n",
    "        n = len(candidates)\n",
    "        candidates.sort()\n",
    "        ans = []\n",
    "        dfs(0, [], target)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        # candidates = list(set(candidates))\n",
    "        res = []\n",
    "        candidates.sort()\n",
    "        self.dfs(candidates, 0, target, [], res)\n",
    "        return res\n",
    "    \n",
    "    def dfs(self, candidates, start_idx, target, sub_res, res):\n",
    "        if target == 0:\n",
    "            res.append(sub_res.copy())\n",
    "            return\n",
    "        \n",
    "        for i in range(start_idx, len(candidates)):\n",
    "            if candidates[i] > target: return\n",
    "            if i != start_idx and candidates[i] == candidates[i - 1]: continue\n",
    "            sub_res.append(candidates[i])\n",
    "            self.dfs(candidates, i + 1, target - candidates[i], sub_res, res)\n",
    "            sub_res.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        candidates.sort()\n",
    "\n",
    "        res = []\n",
    "        def backtrace(paths, index):\n",
    "            if sum(paths) == target:\n",
    "                res.append(paths)\n",
    "                return\n",
    "            if sum(paths) > target:\n",
    "                return\n",
    "            for i in range(index, len(candidates)):\n",
    "                if i> index and candidates[i] == candidates[i-1]:\n",
    "                    continue\n",
    "                backtrace(paths + [candidates[i]], i+1)\n",
    "        backtrace([], 0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        self.res, n = [], len(candidates)\n",
    "        candidates = sorted(candidates)\n",
    "        temp, temp_sum = [0]*n, 0\n",
    "\n",
    "        def bt(idx, ava, temp_sum):\n",
    "            if idx==n: return True\n",
    "            for i in range(ava, n):\n",
    "                # 因为已经排序，所以后一层选择的数一定大于前一层（保证了解排列单调增）\n",
    "                # 因此在同一层中（一个i循环）选择同样大小的数对应了相同的最终结果，去重即同样的数在同一层只排列一次，不影响相同数多层重复\n",
    "                if i>ava and candidates[i]==candidates[i-1]: continue\n",
    "                temp[idx] = candidates[i]\n",
    "                if temp_sum+candidates[i]==target: self.res.append(temp[:idx+1])\n",
    "                # 有序数组剪枝\n",
    "                elif temp_sum+candidates[i]>target: break\n",
    "                bt(idx+1, i+1, temp_sum+candidates[i])\n",
    "                # 引入temp_sum避免反复求和\n",
    "\n",
    "        bt(0, 0, 0)\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        res=[]\n",
    "        tmp=[]\n",
    "        t=0\n",
    "        l=min(candidates)\n",
    "        def func(candidates,target,t):\n",
    "            if target==0:\n",
    "                res.append(tmp.copy())\n",
    "            elif target<l:\n",
    "                None\n",
    "            else:\n",
    "                for i in range(t,len(candidates)):\n",
    "                    if i>t and candidates[i] == candidates[i-1]:\n",
    "                        continue\n",
    "                    tmp.append(candidates[i])\n",
    "                    func(candidates,target-candidates[i],i+1)\n",
    "                    tmp.pop()\n",
    "        candidates.sort()\n",
    "        func(candidates,target,t)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        candidates.sort()\n",
    "        nums=[]\n",
    "        cur=0\n",
    "        for i in candidates:\n",
    "            if i==cur:\n",
    "                nums[-1][1]+=1\n",
    "            else:\n",
    "                nums.append([i,1])\n",
    "                cur=i\n",
    "\n",
    "        squence=[]\n",
    "        res=[]\n",
    "\n",
    "        # print(nums)\n",
    "        def dfs(index,sum_val):\n",
    "            nonlocal squence\n",
    "            nonlocal res\n",
    "            if sum_val==target:\n",
    "                res.append(squence[:])\n",
    "            if index==len(nums) or sum_val+nums[index][0]>target:\n",
    "                return\n",
    "            \n",
    "            for i in range(nums[index][1]):\n",
    "                squence.append(nums[index][0])\n",
    "                dfs(index+1,sum_val+(i+1)*nums[index][0])\n",
    "            squence=squence[:-nums[index][1]]\n",
    "\n",
    "            dfs(index+1,sum_val)\n",
    "            return\n",
    "        dfs(0,0)\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        def quick_sort(sort_list, start, end):\n",
    "            if start>=end:\n",
    "                return\n",
    "            low,high,mid = start,end,sort_list[start]\n",
    "            while high>low:\n",
    "                while high>low and sort_list[high] >= mid:\n",
    "                    high -= 1\n",
    "                sort_list[low] = sort_list[high]\n",
    "                while high>low and sort_list[low]<mid:\n",
    "                    low+=1\n",
    "                sort_list[high] = sort_list[low]\n",
    "\n",
    "            sort_list[low] = mid\n",
    "            quick_sort(sort_list, start, low-1)\n",
    "            quick_sort(sort_list, low+1, end)\n",
    "        quick_sort(candidates, 0, len(candidates)-1)\n",
    "\n",
    "        print(candidates)\n",
    "        ans = []\n",
    "        path = []\n",
    "        def dfs(i, t):\n",
    "            if t==0 :\n",
    "                ans.append(path.copy())\n",
    "                return\n",
    "            \n",
    "            for j in range(i+1, len(candidates)):\n",
    "                if j > i + 1 and candidates[j] == candidates[j-1]:\n",
    "                    continue\n",
    "                if candidates[j] > t:\n",
    "                    break\n",
    "                \n",
    "                path.append(candidates[j])\n",
    "                dfs(j, t-candidates[j])\n",
    "                path.pop()\n",
    "        \n",
    "        dfs(-1, target)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        num=len(candidates)\n",
    "        candidates.sort()\n",
    "        res=[]\n",
    "        if sum(candidates)<target:\n",
    "            return []\n",
    "        elif sum(candidates)==target:\n",
    "            return [candidates]\n",
    "        def dfs(s,n):\n",
    "            if sum(s)>target or n==num:\n",
    "                if sum(s)==target:\n",
    "                    if s not in res:\n",
    "                        res.append(s)\n",
    "                return\n",
    "            if sum(s)==target:\n",
    "                if s not in res:\n",
    "                    res.append(s)\n",
    "                return\n",
    "            for i in range(n,num):\n",
    "                dfs(s+[candidates[i]],i+1)\n",
    "        dfs([],0)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        self.res = []\n",
    "        self.path = []\n",
    "        candidates.sort()\n",
    "        self.used = [0 for _ in range(len(candidates))]\n",
    "\n",
    "        def poor(candidates, target, sums, idx, used):\n",
    "            if sums > target:\n",
    "                return \n",
    "            if sums == target:\n",
    "                self.res.append(self.path.copy())\n",
    "\n",
    "            for i in range(idx, len(candidates)):\n",
    "                if i > 0 and candidates[i] == candidates[i - 1] and not self.used[i - 1]:\n",
    "                    continue\n",
    "                self.path.append(candidates[i])\n",
    "                self.used[i] = 1\n",
    "                poor(candidates, target, sums + candidates[i], i + 1, self.used)\n",
    "                self.used[i] = 0\n",
    "                self.path.pop()\n",
    "\n",
    "        poor(candidates, target, 0, 0, self.used)\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        candidate_info = {}\n",
    "        for candidate in candidates:\n",
    "            candidate_info[candidate] = candidate_info.get(candidate, 0) + 1\n",
    "        candidate_keys = list(candidate_info.keys())\n",
    "        candidate_keys.sort()\n",
    "        \n",
    "        def dfs(temp, index, rest):\n",
    "            temp = temp[::]\n",
    "            if rest == 0:\n",
    "                result.append(temp)\n",
    "                return\n",
    "            if rest < 0 or index == len(candidate_keys):\n",
    "                return\n",
    "            dfs(temp, index + 1, rest)\n",
    "            for i in range(candidate_info[candidate_keys[index]]):\n",
    "                temp.append(candidate_keys[index])\n",
    "                rest -= candidate_keys[index]\n",
    "                if rest < 0:\n",
    "                    break\n",
    "                dfs(temp, index + 1, rest)\n",
    "        \n",
    "        result = []\n",
    "        dfs([], 0, target)\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        self.cur = []\n",
    "        self.ans = []\n",
    "        self.c = Counter(candidates)\n",
    "        self.s = [i for i in self.c]\n",
    "\n",
    "        def dfs(pos, t):\n",
    "            if pos == len(self.c) and t == 0:\n",
    "                self.ans.append(self.cur.copy())\n",
    "                return\n",
    "\n",
    "            if pos >= len(self.c) or t < 0:\n",
    "                return\n",
    "\n",
    "            for i in range(self.c[self.s[pos]] + 1):\n",
    "                self.cur += [self.s[pos]] * i\n",
    "                dfs(pos + 1, t - self.s[pos] * i)\n",
    "                if i > 0:\n",
    "                    self.cur = self.cur[:-i]\n",
    "        \n",
    "        dfs(0, target)\n",
    "        return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        candidates=sorted(candidates)\n",
    "        path,res=[],[]\n",
    "        def dfs(startindex):\n",
    "            if sum(path)>target:\n",
    "                return\n",
    "            elif sum(path)==target:\n",
    "                res.append(path.copy())\n",
    "                return\n",
    "            set1=set()\n",
    "            for i in range(startindex,len(candidates)):\n",
    "                if candidates[i] in set1:\n",
    "                    continue\n",
    "                set1.add(candidates[i])\n",
    "                path.append(candidates[i])\n",
    "                dfs(i+1)\n",
    "                path.pop()\n",
    "        dfs(0)\n",
    "        return res\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        candidates.sort()\n",
    "        path=[]\n",
    "        ans=[]\n",
    "        def backtrack(k,t):\n",
    "            for i,x in enumerate(k):\n",
    "                if t<x:\n",
    "                    break\n",
    "                elif t==x:\n",
    "                    if path+[x] not in ans:\n",
    "                        ans.append(path+[x])\n",
    "                else:\n",
    "                    path.append(x)\n",
    "                    backtrack(k[i+1:],t-x)\n",
    "                    path.pop()\n",
    "        backtrack(candidates,target)\n",
    "        return ans\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        candidates.sort()\n",
    "        n = len(candidates)\n",
    "        self.ret = []\n",
    "        def bt(i, s, l):\n",
    "            if s == target:\n",
    "                self.ret.append([ candidates[i] for i in l ])\n",
    "            elif i == n or s > target:\n",
    "                return\n",
    "            else:    \n",
    "                if (i > 0 and candidates[i] == candidates[i - 1]) and (not l or l[-1] != i - 1):\n",
    "                    can_pick = 0\n",
    "                else:\n",
    "                    can_pick = 1\n",
    "\n",
    "                if can_pick:\n",
    "                    l.append(i)\n",
    "                    bt(i + 1, s + candidates[i], l)\n",
    "                    l.pop()\n",
    "\n",
    "                bt(i + 1, s, l)\n",
    "        bt(0, 0, [])\n",
    "        return self.ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        n = len(candidates)\n",
    "        res=[]\n",
    "        candidates.sort()\n",
    "        print(candidates)\n",
    "        def backtrack(start,tmp_res,target):\n",
    "            if target ==0:\n",
    "                if tmp_res[:] not in res:\n",
    "                    res.append(tmp_res[:])\n",
    "            \n",
    "            for i in range(start,n):\n",
    "                if candidates[i] <= target:\n",
    "                    tmp_res.append(candidates[i])\n",
    "                    backtrack(i+1,tmp_res,target-candidates[i])\n",
    "                    tmp_res.pop()\n",
    "                else:\n",
    "                    break\n",
    "\n",
    "        backtrack(0,[],target)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        results = []\n",
    "\n",
    "        candidates.sort()\n",
    "        print(candidates)\n",
    "        def dfs(paths, index):\n",
    "            if sum(paths) == target:# and sorted(paths) not in results:\n",
    "                results.append(paths)\n",
    "                return\n",
    "            if sum(paths)> target:\n",
    "                return\n",
    "\n",
    "            for i in range(index, len(candidates)):\n",
    "                if i> index and candidates[i] in candidates[index:i]:\n",
    "                    continue\n",
    "                dfs(paths +[candidates[i]], i+1)\n",
    "\n",
    "        dfs([], 0)\n",
    "        print(results)\n",
    "        return results"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        n_list = []\n",
    "        result = []\n",
    "        candidates.sort()\n",
    "\n",
    "        def dfs(i):\n",
    "            if i == len(candidates):\n",
    "                return\n",
    "            n_list.append(candidates[i])\n",
    "            sum_n = sum(n_list)\n",
    "            if sum_n == target:\n",
    "                result.append(n_list.copy())\n",
    "            elif sum_n < target:\n",
    "                j = i + 1\n",
    "                while j < len(candidates):\n",
    "                    dfs(j)\n",
    "                    j += 1\n",
    "                    while j < len(candidates) and candidates[j] == candidates[j-1]:\n",
    "                        j += 1\n",
    "            n_list.pop()\n",
    "\n",
    "        for i in range(0, len(candidates)):\n",
    "            if i != 0 and candidates[i] == candidates[i-1]:\n",
    "                continue\n",
    "            dfs(i)\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        candidates.sort()\n",
    "        n = len(candidates)\n",
    "        ans =[]\n",
    "        path =[] \n",
    "        \n",
    "\n",
    "        def dfs(i):\n",
    "            if sum(path)==target:\n",
    "                path.sort()\n",
    "                ans.append(path.copy())\n",
    "                return\n",
    "            if sum(path)>target:\n",
    "                return\n",
    "\n",
    "            for j in range(i,n):\n",
    "                if candidates[j]==candidates[j-1] and j-1>=i:\n",
    "                    continue\n",
    "                path.append(candidates[j])\n",
    "                dfs(j+1)\n",
    "                path.pop() #恢复现场\n",
    "\n",
    "        dfs(0)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        def dfs(pos: int, rest: int):\n",
    "            nonlocal sequence\n",
    "            if rest == 0:\n",
    "                ans.append(sequence[:])\n",
    "                return\n",
    "            if pos == len(freq) or rest < freq[pos][0]:\n",
    "                return\n",
    "            \n",
    "            dfs(pos + 1, rest)\n",
    "\n",
    "            most = min(rest // freq[pos][0], freq[pos][1])\n",
    "            for i in range(1, most + 1):\n",
    "                sequence.append(freq[pos][0])\n",
    "                dfs(pos + 1, rest - i * freq[pos][0])\n",
    "            sequence = sequence[:-most]\n",
    "        \n",
    "        freq = sorted(collections.Counter(candidates).items())\n",
    "        ans = list()\n",
    "        sequence = list()\n",
    "        dfs(0, target)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        # 遍历数据类型和出现次数\n",
    "        def dfs(num_i,rest):\n",
    "            nonlocal now_list\n",
    "            if(rest == 0):\n",
    "                res.append(now_list.copy())\n",
    "                return \n",
    "            if(num_i == n or rest < num_cnt[num_i][0]):\n",
    "                return \n",
    "\n",
    "            # 不加入\n",
    "            dfs(num_i + 1, rest)\n",
    "            # 加入\n",
    "            all_cnt = num_cnt[num_i][1]\n",
    "            num = num_cnt[num_i][0]\n",
    "            for i in range(1,all_cnt + 1):\n",
    "                now_list.append(num)\n",
    "                dfs(num_i + 1,rest - num * i)\n",
    "            now_list = now_list[:-all_cnt]\n",
    "            return \n",
    "\n",
    "        \n",
    "        num_cnt = sorted(Counter(candidates).items())\n",
    "        n = len(num_cnt)\n",
    "        now_list = []\n",
    "        res = []\n",
    "        dfs(0,target)\n",
    "        return res\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        def dfs(idx, s):\n",
    "            if s > target or s + sum(candidates[idx:]) < target:\n",
    "                return\n",
    "            if s == target:\n",
    "                res.add(tuple(path[:]))\n",
    "                return\n",
    "            path.append(candidates[idx])\n",
    "            dfs(idx+1, s+candidates[idx])\n",
    "            path.pop(-1)\n",
    "            dfs(idx+1, s)\n",
    "        res = set()\n",
    "        path = []\n",
    "        l = len(candidates)\n",
    "        candidates = sorted(candidates)\n",
    "        dfs(0, 0)\n",
    "        return list(map(list, res))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        self.ans = []\n",
    "        #解集不能包含重复的组合。 \n",
    "        candidates = sorted(candidates)\n",
    "        self.visited= {}\n",
    "        def dfs(candidates,level, target, path):\n",
    "            if target == 0:\n",
    "                self.ans.append(path)\n",
    "                return \n",
    "            if level == len(candidates):\n",
    "                return \n",
    "            if target <0 :\n",
    "                return \n",
    "            #如果前面一样且没用，则后面不能用\n",
    "            if level>0 and candidates[level] == candidates[level-1] and not self.visited[candidates[level]]:\n",
    "                pass  \n",
    "            else:\n",
    "                self.visited[candidates[level]]=True\n",
    "                dfs(candidates, level+1, target-candidates[level], path+[candidates[level]])\n",
    "                self.visited[candidates[level]]=False\n",
    "            #这个没用\n",
    "            dfs(candidates, level+1, target, path)\n",
    "        \n",
    "        dfs(candidates, 0, target, [])\n",
    "        return self.ans \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def combination(\n",
    "        self,\n",
    "        target: int,\n",
    "        uniqs: List[int],\n",
    "        count: List[int],\n",
    "        start: int,\n",
    "        picked: List[int],\n",
    "        acc: int,\n",
    "        collect: List[List[int]],\n",
    "    ) -> None:\n",
    "        if acc >= target:\n",
    "            if acc == target:\n",
    "                collect.append(picked[:])\n",
    "            return\n",
    "            \n",
    "        for i in range(start, len(uniqs)):\n",
    "            for c in range(count[i]):\n",
    "                picked.append(uniqs[i])\n",
    "                acc += uniqs[i]\n",
    "                self.combination(target, uniqs, count, i + 1, picked, acc, collect)\n",
    "            acc -= uniqs[i] * count[i]\n",
    "            del picked[-count[i]:]\n",
    "\n",
    "\n",
    "    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        freqs: Dict[int, int] = Counter(candidates)\n",
    "        uniqs: List[int] = list(freqs.keys())\n",
    "        count: List[int] = [freqs[n] for n in uniqs]\n",
    "\n",
    "        answer: List[List[int]] = []\n",
    "        self.combination(target, uniqs, count, 0, [], 0, answer)\n",
    "        return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum2(self, candidates, target):\n",
    "        \"\"\"\n",
    "        :type candidates: List[int]\n",
    "        :type target: int\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        self.result = []\n",
    "        candidates.sort()\n",
    "        self.recur(candidates, target, 0, [], 0)\n",
    "        \n",
    "        return self.result\n",
    "        \n",
    "    def recur(self, candidates, target, start, curr, cur_sum):\n",
    "        for i in range(start, len(candidates)):\n",
    "            if cur_sum + candidates[i] > target:\n",
    "                return\n",
    "            elif cur_sum + candidates[i] == target:\n",
    "                if (curr + [candidates[i]]) not in self.result:\n",
    "                    self.result.append(curr + [candidates[i]])\n",
    "                return\n",
    "            else:\n",
    "                self.recur(candidates, target, i+1, curr + [candidates[i]], cur_sum + candidates[i])\n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum2(self, candidates, target):\n",
    "        \"\"\"\n",
    "        :type candidates: List[int]\n",
    "        :type target: int\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        def bt(res, cur, arr, i, t):\n",
    "            if t < 0:\n",
    "                return\n",
    "            elif t == 0:\n",
    "                res.append(cur[:])\n",
    "            elif i < len(arr):\n",
    "                cur.append(arr[i])\n",
    "                bt(res, cur, arr, i + 1, t - arr[i])\n",
    "                cur.pop()\n",
    "                j = i + 1\n",
    "                while j < len(arr) and arr[i] == arr[j]:\n",
    "                    j += 1\n",
    "                bt(res, cur, arr, j, t)\n",
    "        res = []\n",
    "        bt(res, [], sorted(candidates), 0, target)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum2(self, candidates, target):\n",
    "        \"\"\"\n",
    "        :type candidates: List[int]\n",
    "        :type target: int\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        if not isinstance(candidates, list) or not isinstance(target, int):\n",
    "            return\n",
    "        if not candidates:\n",
    "            return [[]]\n",
    "        candidates.sort()\n",
    "        answer, result = [], []\n",
    "        self.combinationSum2_Core(candidates, target, 0, answer, result)\n",
    "        if candidates[-1] == target:\n",
    "            result.append([candidates[-1]])\n",
    "        reList = list(set([tuple(t) for t in result]))\n",
    "        reList = [list(v) for v in reList]\n",
    "        return reList\n",
    "\n",
    "    def combinationSum2_Core(self, candidates, target, start, answer, result):\n",
    "        if target == 0:\n",
    "            temp = answer[:]\n",
    "            result.append(temp)\n",
    "        if start == len(candidates):\n",
    "            return\n",
    "        for Index in range(start, len(candidates)):\n",
    "            if target > 0:\n",
    "                answer.append(candidates[Index])\n",
    "                self.combinationSum2_Core(candidates, target - candidates[Index], Index + 1, answer, result)\n",
    "                answer.pop()\n",
    "            elif target < 0:\n",
    "                return\n",
    "            else:\n",
    "                temp = answer[:]\n",
    "                result.append(temp)\n",
    "                return"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum2(self, candidates, target):\n",
    "        \"\"\"\n",
    "        :type candidates: List[int]\n",
    "        :type target: int\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "\n",
    "        def dfs(cand,res,index,target,path):\n",
    "            if target == 0:\n",
    "                res.append(path)\n",
    "                return \n",
    "            if target < 0:\n",
    "                return\n",
    "            for i in range(index,len(cand)):\n",
    "                if i!=index and cand[i] == cand[i-1]:\n",
    "        #if i == index,那么下一次dfstarget = target-cand[i] =0，直接返回一次输出结果\n",
    "                    continue\n",
    "                dfs(cand,res,i+1,target-cand[i],path+[cand[i]])\n",
    "        res = []\n",
    "        candidates.sort()\n",
    "        dfs(candidates,res,0,target,[])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum2(self, candidates, target):\n",
    "        \"\"\"\n",
    "        :param candidates: 无重复元素的数组\n",
    "        :param target: 目标数\n",
    "        :return: 解集中的组合\n",
    "        \"\"\"\n",
    "        result = []\n",
    "        candidates.sort()\n",
    "        self.dfs(candidates, target, 0, [], result)\n",
    "        return result\n",
    "\n",
    "    def dfs(self, candidates, target, index, path, result):\n",
    "        if target < 0:\n",
    "            return\n",
    "        if target == 0 and path not in result:\n",
    "            result.append(path)\n",
    "        for i in range(index, len(candidates)):  # 这是为了避免重复\n",
    "                self.dfs(candidates, target-candidates[i], i+1, path+[candidates[i]], result)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum2(self, candidates, target):\n",
    "        \"\"\"\n",
    "        :type candidates: List[int]\n",
    "        :type target: int\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        nc = {}\n",
    "        for i in candidates:\n",
    "            if i in nc:\n",
    "                nc[i] += 1\n",
    "            else:\n",
    "                nc[i] = 1\n",
    "        vals = []\n",
    "        for i in nc:\n",
    "            vals.append(i)\n",
    "        \n",
    "        cals = {}\n",
    "        def dynamic(i, s):\n",
    "            if s == 0:\n",
    "                return [[]]\n",
    "            if s < 0:\n",
    "                return []\n",
    "            if i >= len(nc):\n",
    "                return []\n",
    "            if (i, s) in cals:\n",
    "                return cals[(i, s)]\n",
    "            ans = []\n",
    "            for j in range(nc[vals[i]]+1):\n",
    "                for r in dynamic(i+1, s-j*vals[i]):\n",
    "                    ans.append([vals[i]]*j + r)\n",
    "            cals[(i, s)] = ans\n",
    "            return ans\n",
    "        \n",
    "        return dynamic(0, target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def combinationSum2(self, candidates, target):\n",
    "        \"\"\"\n",
    "        :type candidates: List[int]\n",
    "        :type target: int\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        ans = []\n",
    "        xcandidates = candidates\n",
    "\n",
    "\n",
    "        def get_counter_from_list(xlist):\n",
    "            xcount = Counter()\n",
    "            for item in xlist:\n",
    "                xcount[item] += 1\n",
    "            return xcount\n",
    "\n",
    "        def sum(numlist):\n",
    "            xsum = 0\n",
    "            for item in numlist:\n",
    "                xsum += item\n",
    "            return xsum\n",
    "\n",
    "        def backtrace(nums, start):\n",
    "            xsum = sum(nums)\n",
    "            if xsum == target:\n",
    "                ans.append(nums)\n",
    "            for i, item in enumerate(xcandidates):\n",
    "                if i <= start:\n",
    "                    continue\n",
    "                if xsum + item <= target:\n",
    "                    nums_next = list(nums)\n",
    "                    nums_next.append(item)\n",
    "                    backtrace(nums_next, i)\n",
    "\n",
    "        backtrace([], -1)\n",
    "\n",
    "        # get set\n",
    "        xsetlst = list()\n",
    "        ret_ans = list()\n",
    "        for i, xlist in enumerate(ans):\n",
    "            xset = get_counter_from_list(xlist)\n",
    "            if xset not in xsetlst:\n",
    "                xsetlst.append(xset)\n",
    "                ret_ans.append(xlist)\n",
    "\n",
    "        return ret_ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum2(self, candidates, target):\n",
    "        \"\"\"\n",
    "        :type candidates: List[int]\n",
    "        :type target: int\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        candidates.sort()\n",
    "        dp = [[set() for i in range(target + 1)] for j in candidates]\n",
    "        for j in range(len(candidates)):\n",
    "            dp[j][0].add(\"\")\n",
    "        if candidates[0] <= target:\n",
    "            dp[0][candidates[0]].add(str(candidates[0]))\n",
    "        for j in range(1, len(candidates)):\n",
    "            n = candidates[j]\n",
    "            for i in range(1, target + 1):\n",
    "                dp[j][i].update(dp[j-1][i])\n",
    "                if i >= n:\n",
    "                    for s in dp[j-1][i-n]:\n",
    "                        l = s.split()\n",
    "                        if l and n < int(l[-1]):\n",
    "                            continue\n",
    "                        l.append(str(n))\n",
    "                        dp[j][i].add(' '.join(l))\n",
    "        ans = [[int(n) for n in s.split()] for s in dp[len(candidates)-1][target]]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    def combinationSum2(self, candidates, target):\n",
    "        \n",
    "        all_combs = [[] for i in range(target+1)]\n",
    "        all_combs_ele = [[] for i in range(target+1)]\n",
    "        \n",
    "        \n",
    "        for i in range(len(candidates)):\n",
    "            for t in range(1,target+1):\n",
    "                combs = all_combs[t]\n",
    "                combs_ele = all_combs_ele[t]\n",
    "                temp = str(i)+\";\"+str(candidates[i])\n",
    "                if t == candidates[i]:\n",
    "                    combs.append([candidates[i]])\n",
    "                    combs_ele.append({temp})\n",
    "                \n",
    "                for j in range(len(combs)):\n",
    "                    comb = combs[j]\n",
    "                    comb_ele = combs_ele[j]\n",
    "                    if temp in comb_ele:\n",
    "                        continue\n",
    "                    \n",
    "                    new_sum = candidates[i] + sum(comb)\n",
    "                    if  new_sum <= target:\n",
    "                        all_combs[new_sum].append(comb+[candidates[i]])\n",
    "                        all_combs_ele[new_sum].append(comb_ele | {temp})\n",
    "        \n",
    "        \n",
    "        result_list = []\n",
    "        result_repeat_set = set()\n",
    "        for ele_list in all_combs[-1]:\n",
    "            ele_list.sort()\n",
    "            temp = ','.join('%s' % id for id in ele_list)\n",
    "            if temp in result_repeat_set:\n",
    "                continue\n",
    "            else:\n",
    "                result_list.append(ele_list)\n",
    "                result_repeat_set.add(temp)\n",
    "        \n",
    "        return result_list\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    def recursion(self,candidates,target,tem,res,used):\n",
    "        if target == 0:\n",
    "            res.append(tem[:])\n",
    "            return\n",
    "        if target < 0:\n",
    "            return\n",
    "        for i in range(len(candidates)):\n",
    "            if not used[i]:\n",
    "                tem.append(candidates[i])\n",
    "                used[i] = True\n",
    "                self.recursion(candidates,target-candidates[i],tem,res,used)\n",
    "                tem.pop()\n",
    "                used[i] = False\n",
    "            \n",
    "        \n",
    "    def combinationSum2(self, candidates, target):\n",
    "        \"\"\"\n",
    "        :type candidates: List[int]\n",
    "        :type target: int\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        used = [False]*len(candidates)\n",
    "        res,tem = [],[]\n",
    "        self.recursion(candidates,target,tem,res,used)\n",
    "        res2 =[]\n",
    "        for item in res:\n",
    "            item.sort()\n",
    "            if item not in res2:\n",
    "                res2.append(item)\n",
    "        return res2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        ans = []\n",
    "        candidates.sort()\n",
    "        length = len(candidates)\n",
    "\n",
    "        def backtrack(val=0, tmpli=[], start_idx=0):\n",
    "            if val == target and tmpli not in ans:\n",
    "                ans.append(copy.deepcopy(tmpli))\n",
    "                return\n",
    "            for idx in range(start_idx, length):\n",
    "                candidate = candidates[idx]\n",
    "                if val+candidate > target:\n",
    "                    return\n",
    "                else:\n",
    "                    tmpli.append(candidate)\n",
    "                    backtrack(val+candidate, tmpli, idx+1)\n",
    "                    tmpli.pop(-1)\n",
    "        \n",
    "        backtrack()\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        size = len(candidates)\n",
    "        if size == 0 :\n",
    "            return []\n",
    "        candidates.sort()\n",
    "        res = []\n",
    "        path = []\n",
    "        self.__dfs(candidates,0,target,res,path,size)\n",
    "        return res\n",
    "    def __dfs(self,candidates,begin,residue,res,path,size):\n",
    "        if residue == 0:\n",
    "            res.append(path[:])\n",
    "            return\n",
    "        for index in range(begin,size):\n",
    "            # residue = residue - candidates[index]\n",
    "            if residue - candidates[index]< 0:\n",
    "                break\n",
    "            if index > begin and candidates[index - 1] == candidates[index]:\n",
    "                continue\n",
    "            path.append(candidates[index])\n",
    "            self.__dfs(candidates,index + 1,residue - candidates[index],res,path,size)  #这里要传入index + 1\n",
    "            path.pop()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        if not candidates or not target:\n",
    "            return []\n",
    "\n",
    "        candidates.sort()\n",
    "        if target < candidates[0]:\n",
    "            return []\n",
    "\n",
    "        for i in range(len(candidates)):\n",
    "            if candidates[i] > target:\n",
    "                candidates = candidates[:i]\n",
    "                break\n",
    "               \n",
    "        self.ans = []\n",
    "        self.solve(candidates, target, 0 ,[])\n",
    "        return self.ans\n",
    "\n",
    "    def solve(self,candidates, target, start, add):\n",
    "        if target == 0:\n",
    "            self.ans.append(add)\n",
    "            return \n",
    "        if target < 0:\n",
    "            return\n",
    "        for i in range(start, len(candidates)):\n",
    "            if candidates[i] > target:\n",
    "                return\n",
    "            if i != start and candidates[i] == candidates[i-1]:\n",
    "                continue\n",
    "            self.solve(candidates, target - candidates[i], i+1, add + [candidates[i]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        candidates.sort()\n",
    "        n = len(candidates)\n",
    "        res = []\n",
    "        def backtrack(i, tmp_sum, tmp):\n",
    "            if tmp_sum == target:\n",
    "                res.append(tmp)\n",
    "                return \n",
    "            if  tmp_sum > target:\n",
    "                return \n",
    "            for j in range(i, n):\n",
    "                if tmp_sum + candidates[j] > target:\n",
    "                    break\n",
    "                if j > i and candidates[j] == candidates[j-1]:\n",
    "                    continue\n",
    "                backtrack(j + 1,tmp_sum + candidates[j],tmp+[candidates[j]])\n",
    "        backtrack(0, 0, [])\n",
    "        return res\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        size=len(candidates)\n",
    "        if target<0:\n",
    "            return []\n",
    "        candidates.sort()\n",
    "        res=[]\n",
    "        path=[]\n",
    "        self.search(candidates,target,0,size,path,res)\n",
    "        return res\n",
    "\n",
    "    def search(self,candidates,target,begin,end,path,res):\n",
    "        if target==0:\n",
    "            res.append(path[:])\n",
    "            return\n",
    "\n",
    "        for i in range(begin,end):\n",
    "            if i>begin and candidates[i]==candidates[i-1]:\n",
    "                continue\n",
    "            resident = target-candidates[i]\n",
    "            if resident<0:\n",
    "                break\n",
    "            path.append(candidates[i])\n",
    "            self.search(candidates,resident,i+1,end,path,res)\n",
    "            path.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        if not candidates:\n",
    "            return []\n",
    "        res = []\n",
    "        path = []\n",
    "        candidates.sort()\n",
    "\n",
    "        def backtrack(index, sumvalue):\n",
    "            if sumvalue == target:\n",
    "                if path not in res:\n",
    "                    res.append(path[:])\n",
    "                    return\n",
    "            \n",
    "            for i in range(index, len(candidates)):\n",
    "                if sumvalue > target:\n",
    "                    continue\n",
    "                path.append(candidates[i])\n",
    "                backtrack(i+1, sumvalue+candidates[i])\n",
    "                path.pop()\n",
    "\n",
    "        backtrack(0,0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum2(self, candidates:List[int], target:int) -> List[List[int]]:\n",
    "        res = []\n",
    "        list = []\n",
    "        \n",
    "        def dfs(candidates, i, target):\n",
    "            if target == 0:\n",
    "                list.sort()\n",
    "                if list not in res:\n",
    "                    res.append(list[:])\n",
    "                return\n",
    "            \n",
    "            for index in range(i,len(candidates)):\n",
    "#                 print(i)\n",
    "                if candidates[index]>target:\n",
    "                    break\n",
    "            \n",
    "                if index>i and candidates[index]==candidates[index-1]:\n",
    "                    continue\n",
    "                list.append(candidates[index])\n",
    "                dfs(candidates, index+1, target - candidates[index])\n",
    "                list.remove(candidates[index])\n",
    "        candidates = sorted(candidates)        \n",
    "        dfs(candidates, 0, target)\n",
    "        return res\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        def dfs(n,start,target,path):\n",
    "            if target==0: \n",
    "                res.append(path[:])\n",
    "                return \n",
    "            elif target<0 or n>=N:return   \n",
    "            for i in range(start,len(candidates)):\n",
    "                if visited[i] or(i>0 and candidates[i]==candidates[i-1] and not visited[i-1]):continue\n",
    "                \n",
    "                path.append(candidates[i])\n",
    "                visited[i] = True\n",
    "                dfs(n+1,i+1,target-candidates[i],path)\n",
    "                #print(visited)\n",
    "                path.pop()\n",
    "                visited[i] = False\n",
    "        path = []\n",
    "        candidates.sort()\n",
    "        N = len(candidates)\n",
    "        res = []\n",
    "        visited = [False]*N\n",
    "        dfs(0,0,target,path)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "\n",
    "        candidates = sorted(candidates)\n",
    "        i = 0\n",
    "        out = []\n",
    "        \n",
    "        while i < len(candidates):\n",
    "            if candidates[i] == target:\n",
    "                i += 1\n",
    "                out.append([target])\n",
    "            elif candidates[i] > target:\n",
    "                return out\n",
    "            else:\n",
    "                num = i\n",
    "                sub_target = target\n",
    "                sub_out = []\n",
    "                while num < len(candidates):  # 错误，不一定要用。\n",
    "                    if candidates[i] < sub_target:\n",
    "                        sub_out.append(candidates[num])\n",
    "                        sub_target = target - candidates[num]\n",
    "                        num += 1\n",
    "                    if sub_target == 0:\n",
    "                        out.append(sub_out)\n",
    "                        break\n",
    "                    elif sub_target < 0:\n",
    "                        break\n",
    "        return out\n",
    "\"\"\"\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        candidates = sorted(candidates)\n",
    "        out = []\n",
    "        sub_out = []\n",
    "        if not candidates:\n",
    "            return []\n",
    "        if target <= 0:\n",
    "            return []\n",
    "        def DFS(nums, sub_out, target):\n",
    "            if target < 0:\n",
    "                return \n",
    "            for i in range(len(nums)):\n",
    "                if nums[i] > target:\n",
    "                    return     # 为什么有这么多重复的！！！！\n",
    "                if i + 1 == len(nums):\n",
    "                    if nums[i] == target:\n",
    "                        out.append(sub_out+[nums[i]])\n",
    "                        return \n",
    "                    else:\n",
    "                        return \n",
    "                if nums[i] < target:\n",
    "                    DFS(nums[i+1:], sub_out+[nums[i]], target-nums[i])\n",
    "                    DFS(nums[i+1:], sub_out, target)\n",
    "                elif nums[i] == target:\n",
    "                    out.append(sub_out+[nums[i]])\n",
    "                    return \n",
    "        DFS(candidates, sub_out, target)\n",
    "        return out\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        def dfs(pos: int, rest: int):\n",
    "            nonlocal sequence\n",
    "            if rest == 0:\n",
    "                ans.append(sequence[:])\n",
    "                return\n",
    "            if pos == len(freq) or rest < freq[pos][0]:\n",
    "                return\n",
    "            \n",
    "            dfs(pos + 1, rest)\n",
    "\n",
    "            most = min(rest // freq[pos][0], freq[pos][1])\n",
    "            for i in range(1, most + 1):\n",
    "                sequence.append(freq[pos][0])\n",
    "                dfs(pos + 1, rest - i * freq[pos][0])\n",
    "            sequence = sequence[:-most]\n",
    "        \n",
    "        freq = sorted(collections.Counter(candidates).items())\n",
    "        ans = list()\n",
    "        sequence = list()\n",
    "        dfs(0, target)\n",
    "        return ans\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum2(self, candidates, target):\n",
    "        candidates = sorted(candidates)\n",
    "        sum_all = sum(candidates)\n",
    "        if  sum_all < target:\n",
    "            return []\n",
    "        if sum_all == target:\n",
    "            return [candidates]\n",
    "\n",
    "        out = set()\n",
    "        if not candidates:\n",
    "            return []\n",
    "        if target <= 0:\n",
    "            return []\n",
    "        def DFS(nums, sub_out, target):\n",
    "            if target < 0:\n",
    "                return \n",
    "            for i in range(len(nums)):\n",
    "                if nums[i] > target:\n",
    "                    return\n",
    "                if i + 1 == len(nums):\n",
    "                    if nums[i] == target:\n",
    "                        out.add(tuple(sub_out+[nums[i]]))\n",
    "                        return\n",
    "                    else:\n",
    "                        return \n",
    "                if nums[i] < target:\n",
    "                    # DFS(nums[i + 1:], sub_out, target)  ##问题在这，其实因为for，每个都已经都执行了。                 \n",
    "                    DFS(nums[i+1:], sub_out + [nums[i]], target-nums[i])\n",
    "\n",
    "                elif nums[i] == target:\n",
    "                    out.add(tuple(sub_out+[nums[i]]))\n",
    "                    return \n",
    "        DFS(candidates, [], target)\n",
    "\n",
    "        return list(out)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        if not candidates:\n",
    "            return\n",
    "        res = []\n",
    "        n = len(candidates)\n",
    "        candidates.sort()\n",
    "        def helper(temp, target, i):\n",
    "            if target == 0:\n",
    "                res.append(temp)\n",
    "            elif target < 0:\n",
    "                return\n",
    "            for j in range(i, n):\n",
    "                print(target, candidates[j])\n",
    "                if candidates[j] > target:\n",
    "                    break\n",
    "                if candidates[j] > target or (j > i and candidates[j - 1] == candidates[j]):\n",
    "                    continue\n",
    "                helper(temp + [candidates[j]], target - candidates[j], j + 1)\n",
    "        helper([], target, 0)\n",
    "        return res\n",
    "\n",
    "        # if not candidates:\n",
    "        #     return []\n",
    "        # candidates.sort()\n",
    "        # n = len(candidates)\n",
    "        # res = []\n",
    "        #\n",
    "        # def backtrack(i, tmp_sum, tmp_list):\n",
    "        #     if tmp_sum == target:\n",
    "        #         res.append(tmp_list)\n",
    "        #         return\n",
    "        #     for j in range(i, n):\n",
    "        #         if tmp_sum + candidates[j] > target: break\n",
    "        #         if j > i and candidates[j] == candidates[j - 1]: continue\n",
    "        #         backtrack(j + 1, tmp_sum + candidates[j], tmp_list + [candidates[j]])\n",
    "        #\n",
    "        # backtrack(0, 0, [])\n",
    "        # return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        def dps(index,target):\n",
    "            visited.add(tuple(used))\n",
    "            if target<0:\n",
    "                return\n",
    "            elif target == 0:\n",
    "                res.append(used[::-1])\n",
    "                return\n",
    "            else:\n",
    "                if index+1<len(candidates):\n",
    "                    used.append(candidates[index+1])\n",
    "                    if tuple(used) not in visited:\n",
    "                        dps(index+1,target-candidates[index+1])\n",
    "                    used.pop()\n",
    "                    dps(index+1,target)\n",
    "                else:\n",
    "                    return\n",
    "                        \n",
    "        visited=set()\n",
    "        used=[]\n",
    "        candidates.sort(reverse=True)\n",
    "        res=[]\n",
    "        dps(-1,target)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        candidates = sorted(candidates)\n",
    "        n = len(candidates)\n",
    "        res = []\n",
    "        res2 = {}\n",
    "        res3 = {}\n",
    "        def helper(i, tmp, target):\n",
    "            for j in range(i, n):\n",
    "\n",
    "                use = candidates[j]\n",
    "                if candidates[j]<target:\n",
    "                    if str((tmp, j)) not in res3:\n",
    "                        res3[str((tmp, j))] =1\n",
    "\n",
    "                        helper(j+1, tmp+[use], target-use)\n",
    "\n",
    "                elif candidates[j]==target:\n",
    "                    if str(tmp+[use]) not in res2:\n",
    "                        res2[str(tmp+[use])] = 1\n",
    "                        res.append(tmp+[use])\n",
    "                else:\n",
    "                    return\n",
    "\n",
    "        helper(0,[], target)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "def dfs(candidates, start_pos, remain, path, res):\n",
    "    if remain == 0:\n",
    "        res.append(path.copy())\n",
    "        return\n",
    "    if start_pos == len(candidates):\n",
    "        return\n",
    "    for i in range(start_pos, len(candidates)):\n",
    "        if remain < candidates[i]:\n",
    "            break\n",
    "        if i > start_pos and candidates[i-1] == candidates[i]:\n",
    "            continue\n",
    "        if remain >= candidates[i]:\n",
    "            path.append(candidates[i])\n",
    "            dfs(candidates, i + 1, remain - candidates[i], path, res)\n",
    "            path.pop()\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        candidates.sort()\n",
    "        res = []\n",
    "        dfs(candidates, 0, target, [], res)\n",
    "        return res\n",
    "\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    print(Solution().combinationSum2([3, 1, 3, 5, 1, 1], 8))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.path = []\n",
    "        self.result = []\n",
    "    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        if not candidates:\n",
    "            return []\n",
    "        candidates.sort()\n",
    "        self.back(candidates,target,0,0)\n",
    "        return self.result\n",
    "    def back(self,candidates,target,sum_num,start_index):\n",
    "        if sum_num==target:\n",
    "            self.result.append(self.path[:])\n",
    "        for i in range(start_index,len(candidates)):\n",
    "            if sum_num+candidates[i]>target:\n",
    "                return\n",
    "            # 跳过同一树层使用过的元素\n",
    "            if i > start_index and candidates[i] == candidates[i-1]:\n",
    "                continue\n",
    "            self.path.append(candidates[i])\n",
    "            sum_num+=candidates[i]\n",
    "            self.back(candidates,target,sum_num,i+1)\n",
    "            self.path.pop()\n",
    "            sum_num-=candidates[i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        candidates.sort()\n",
    "\n",
    "        res=[]\n",
    "        def dfs(candidates,target,i,path):\n",
    "            if sum(path)==target and path not in res:\n",
    "                res.append(path[:])\n",
    "            if i==len(candidates):\n",
    "                return\n",
    "            for j in range(i,len(candidates)):\n",
    "                if j > i and candidates[j] == candidates[j-1]:\n",
    "                    continue\n",
    "                path.append(candidates[j])\n",
    "                if sum(path)<=target:\n",
    "                    dfs(candidates,target,j+1,path)\n",
    "                path.pop()\n",
    "\n",
    "        dfs(candidates,target,0,[])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def __init__(self):\n",
    "        self.sum = 0\n",
    "        self.result = []\n",
    "        self.path = []\n",
    "    def combinationSum2(self,candidates, target):\n",
    "        candidates.sort()\n",
    "        def backtracking(target,index):\n",
    "            if self.sum == target:\n",
    "                self.result.append(self.path[:])\n",
    "                return\n",
    "            if self.sum > target:\n",
    "                return\n",
    "\n",
    "            for i in range(index,len(candidates)):\n",
    "                if i > index and candidates[i] == candidates[i-1]:\n",
    "                    continue\n",
    "                self.sum += candidates[i]\n",
    "                self.path.append(candidates[i])\n",
    "                \n",
    "                backtracking(target,i+1)\n",
    "\n",
    "                self.sum -= candidates[i]\n",
    "                self.path.pop()\n",
    "\n",
    "        backtracking(target,0)\n",
    "        return self.result\n",
    "\n",
    "            # last_startidx = n - (k - len(path)) + 1\n",
    "# n = 4\n",
    "# k = 2\n",
    "# print(Solution().combine(n,k))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        # dp[i]: list, 保存和为i的所有不同组合\n",
    "        dp = [[] for _ in range(1 + target)]\n",
    "        dp[0].append([])\n",
    "        times = collections.Counter(candidates)\n",
    "        for c in times.keys():\n",
    "            t = times[c]\n",
    "            Next = [[] for _ in range(1 + target)]\n",
    "            for j in range(1, t + 1):\n",
    "                print(c, t, j)\n",
    "                for i in range(c * j, target + 1):\n",
    "                    # 把dp[i - c]中每个组合的末尾加上c生成新组合\n",
    "                    Next[i] += [s + [c] * j for s in dp[i - c * j]]      \n",
    "            for i in range(target + 1):\n",
    "                dp[i] += Next[i]\n",
    "        return dp[target]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def backtracking(self, candidates, target, index, path, results):\n",
    "        if target == 0:\n",
    "            results.append(path[:])\n",
    "            return\n",
    "        for i in range(index, len(candidates)):\n",
    "            if i > index and candidates[i] == candidates[i-1]:\n",
    "                continue\n",
    "            if candidates[i] > target:\n",
    "                break\n",
    "            path.append(candidates[i])\n",
    "            self.backtracking(candidates, target- candidates[i], i + 1, path, results)\n",
    "            path.pop()\n",
    "        \n",
    "    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        candidates.sort()\n",
    "        results = []\n",
    "        self.backtracking(candidates, target, 0, [], results)\n",
    "        return results"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        candidates.sort()\n",
    "\n",
    "        def dfs(candidates, size, path, res, begin, target):\n",
    "            if target < 0: \n",
    "                return \n",
    "            if target == 0:\n",
    "                res.append(path)\n",
    "                return \n",
    "            for index in range(begin, size):\n",
    "                if index > begin and candidates[index] == candidates[index - 1]: continue\n",
    "                temp = index + 1\n",
    "                dfs(candidates, size, path + [candidates[index]], res, temp, target - candidates[index])\n",
    "\n",
    "        \n",
    "        res = []\n",
    "        size = len(candidates)\n",
    "        if size == 0: return res\n",
    "        path = []\n",
    "        dfs(candidates, size, path, res, 0, target)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "class Solution:\n",
    "    def _combinationSum2(self, candidates, target):\n",
    "        if target == 0:\n",
    "            return [()]\n",
    "        if not candidates or target < 0:\n",
    "            return []\n",
    "        \n",
    "        candidates = candidates.copy()\n",
    "        k0 = list(candidates.keys())[0]\n",
    "        v0 = candidates.pop(k0)\n",
    "\n",
    "        r = []\n",
    "        for i in range(v0 + 1):\n",
    "            r.extend([(*([k0] * i), *r) for r in \n",
    "                self._combinationSum2(candidates, target - k0 * i)])\n",
    "        \n",
    "        return r\n",
    "        \n",
    "    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        return self._combinationSum2(dict(Counter(candidates)), target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def _combinationSum2(self, candidates, target):\n",
    "        if target == 0:\n",
    "            return [[]]\n",
    "        if not candidates or target < 0:\n",
    "            return []\n",
    "        \n",
    "        candidates = candidates.copy()\n",
    "        k0 = list(candidates.keys())[0]\n",
    "        v0 = candidates.pop(k0)\n",
    "\n",
    "        r = []\n",
    "        for i in range(v0 + 1):\n",
    "            r.extend([[k0] * i + r for r in \n",
    "                self._combinationSum2(candidates, target - k0 * i)])\n",
    "        \n",
    "        return r\n",
    "        \n",
    "    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        return self._combinationSum2(dict(Counter(candidates)), target)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
